﻿using GeometricAlg.Model;
using GeometryLibrary.Models;
using System.Collections.Generic;

namespace GeometryLibrary.Algorithms
{
    public static class PointInPolygonDetection
    {
        /// <summary>  
        /// 判断给定的点是否位于给定的多边形内部。  
        /// </summary>  
        /// <param name="point">要判断的点。</param>  
        /// <param name="polygon">多边形对象，包含顶点的列表。</param>  
        /// <returns>如果点在多边形内部，则返回 true；否则返回 false。</returns>  
        public static bool IsPointInsidePolygon(Point2d point, Polygon2d polygon)
        {

            int crossings = 0;
            int j = polygon.Vertices.Count - 1;
            for (int i = 0; i < polygon.Vertices.Count; i++)
            {
                if ((polygon.Vertices[i].Y > point.Y) != (polygon.Vertices[j].Y > point.Y) &&
                    point.X < (polygon.Vertices[j].X - polygon.Vertices[i].X) * (point.Y - polygon.Vertices[i].Y) / (polygon.Vertices[j].Y - polygon.Vertices[i].Y) + polygon.Vertices[i].X)
                {
                    crossings++;
                }
                j = i;
            }

            return (crossings % 2) == 1;
        }

        public static bool PointInRegion1(IEnumerable<Point2d> pts, Point2d targetPoint)
        {
            var ptList = pts.ToList();
            var flag = false;
            var numVertices = ptList.Count;
            if (numVertices < 3)
            {
                return false;
            }

            for (var index = 0; index < numVertices; index++)
            {
                var p1 = ptList[index];
                var p2 = ptList[(index + 1) % numVertices];

                if (p1 == targetPoint || p2 == targetPoint)
                {
                    return false;
                }
                if (targetPoint.Y < Math.Min(p1.Y, p2.Y))
                {
                    continue;
                }
                if (targetPoint.Y >= Math.Max(p1.Y, p2.Y))
                {
                    continue;
                }
                if (targetPoint.X > Math.Max(p1.X, p2.X))
                {
                    continue;
                }
                var vec = p2 - p1;
                var denominator = vec.X;
                if (Math.Abs(denominator) < double.Epsilon)
                {
                    continue;
                }
                var t = (targetPoint.X - p1.X) / denominator;

                if (t >= 0 && t <= 1)
                {
                    var intersectionY = t * vec.Y + p1.Y;
                    if (intersectionY >= targetPoint.Y)
                    {
                        flag = !flag;
                    }
                }
            }

            return flag;
        }

        public static bool PointInRegion2(IEnumerable<Point2d> pts, Point2d targetPoint)
        {
            var ptList = pts.ToList();
            var numVertices = ptList.Count;
            if (numVertices < 3)
            {
                return false;
            }
            var inside = false;

            for (var index = 0; index < numVertices; index++)
            {
                var p1 = ptList[index];
                var p2 = ptList[(index + 1) % numVertices];

                if ((targetPoint.Y == p1.Y && targetPoint.X < p1.Y) || (targetPoint.Y == p2.Y && targetPoint.X < p2.X))
                {
                    var prevIndex = (index - 1 + numVertices) % numVertices;
                    var nextIndex = (index + 1) % numVertices;
                    var prevPoint = ptList[prevIndex];
                    var nextPoint = ptList[nextIndex];

                    if ((targetPoint.Y < prevPoint.Y && targetPoint.Y >= nextPoint.Y) ||
                        (targetPoint.Y >= prevPoint.Y && targetPoint.Y < nextPoint.Y))
                    {
                        inside = !inside;
                    }
                }

                if ((targetPoint.Y < p1.Y != targetPoint.Y < p2.Y)
                    && (targetPoint.Y - p1.Y) / (p2.Y - p1.Y) * (p2.X - p1.X) + p1.X
                    > targetPoint.X)
                {
                    inside = !inside;
                }
            }

            return inside;
        }

        public static bool PointInRegion3(IEnumerable<Point2d> pts, Point2d targetPoint)
        {
            var ptList = pts.ToList();
            var numVertices = ptList.Count;
            if (numVertices < 3)
            {
                return false;
            }
            var inside = false;

            for (var index = 0; index < numVertices; index++)
            {
                var p1 = ptList[index];
                var p2 = ptList[(index + 1) % numVertices];

                if ((targetPoint.Y == p1.Y && targetPoint.X < p1.Y) || (targetPoint.Y == p2.Y && targetPoint.X < p2.X))
                {
                    // 如果射线经过顶点，我们需要检查这个顶点前后的边的方向  
                    var prevIndex = (index - 1 + numVertices) % numVertices;
                    var nextIndex = (index + 1) % numVertices;
                    var prevPoint = ptList[prevIndex];
                    var nextPoint = ptList[nextIndex];

                    // 检查顶点前一条边和顶点后一条边的方向是否一致  
                    if ((targetPoint.Y < prevPoint.Y &&  targetPoint.Y >= nextPoint.Y) ||
                        (targetPoint.Y >= prevPoint.Y && targetPoint.Y < nextPoint.Y))
                    {
                        inside = !inside;
                    }
                }
                else if ((targetPoint.Y < p1.Y != targetPoint.Y < p2.Y))
                {
                    var vec = p2 - p1;

                    var t = (targetPoint.Y - p1.Y) / (p2.Y - p1.Y);

                    var x = t * (p2.X - p1.X) + p1.X;

                    if (x > targetPoint.X && t > 0 && t < 1)
                    {
                        inside = !inside;
                    }
                }
            }
            return inside; 
        }

    }
}